class Solution {
    vector<string> res;
    string path;
    string s;
public:
    void dfs(int block, int pos) {
        string cur = "";
        if (block > 4) {
            if (pos == s.size()) {
                res.push_back(path);
            } else {
                return;
            }
        }
        for (int i = pos; i < pos + 3 && i < s.size(); ++i) {
            cur += s[i];
            int num = stoi(cur);
            string tmp = path;
            if (num <= 255 && (cur.size() == 1 || cur[0] != '0')) {
                if (block < 4) {
                    path += cur + ".";
                } else {
                    path += cur;
                }
                dfs(block+1, i+1);
                path = tmp; // 回溯
            }
        }
    }
    vector<string> restoreIpAddresses(string str) {
        this->s = str;
        int n = s.size();
        if (n <= 3) return res;
        dfs(1, 0);
        return res;
    }
};